package 寒假作业.LeetCode;

public class Num148 {
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode sortList(ListNode head) {
        return sortList(head,null);
    }
    //head和tail用于分割链表
    private ListNode sortList(ListNode head, ListNode tail) {
        if(head == null){
            return head;
        }
        //tail永远都是链表的尾部
        if(head.next == tail){
            head.next = null;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        //当到达链表尾部，用快慢指针进行分割
        while (fast != tail){
            slow = slow.next;
            fast = fast.next;
            if (fast != tail){
                fast = fast.next;
            }
        }
        //中间节点
        ListNode mid = slow;
        //继续递归分割到最小(一个节点)就开始return了。
        ListNode list1 = sortList(head,mid);
        ListNode list2 = sortList(mid,tail);
        //合并两个有序链表
        ListNode sorted = merge(list1,list2);
        return sorted;
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode();
        ListNode temp = dummyHead;
        ListNode temp1 = head1;
        ListNode temp2 = head2;

        while (temp1 != null && temp2 != null){
            if (temp1.val < temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null){
            temp.next = temp1;
        }else if(temp2 != null){
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}













